class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> cur;
        vector<vector<int> > ans;
        combineHelper(n, k, 0, cur, ans);
        return ans;
    }

    void combineHelper(int n, int k, int start, vector<int> &cur, vector<vector<int> > &ans) {
        if (cur.size() == k) {
            ans.push_back(cur);
            return;
        }
        for (int i = start; i < n; ++i) {
            cur.push_back(i + 1);
            combineHelper(n, k, i + 1, cur, ans);
            cur.pop_back();
        }
    }

};
